package main

import (
	"fmt"
	"sync"
)

// 节点数据
type DoubleObject interface{}

// 双链表节点
type DoubleNode struct {
	Data DoubleObject
	Prev *DoubleNode
	Next *DoubleNode
}

// 双链表
type DoubleList struct {
	mu   sync.RWMutex
	Size uint64
	Head *DoubleNode
	Tail *DoubleNode
}

func NewDoubleList() *DoubleList {
	return &DoubleList{
		mu:   sync.RWMutex{},
		Size: 0,
		Head: nil,
		Tail: nil,
	}
}

// 获取指定位置的节点
func (list *DoubleList) Get(index uint64) (value interface{}) {
	if list.Size == 0 || index > list.Size {
		return nil
	}

	if index == 0 {
		return list.Head
	}
	if index == list.Size {
		return list.Tail.Data
	}
	node := list.Head
	var i uint64
	for i = 1; i < index; i++ {
		node = node.Next
	}
	return node.Data
}

// 尾部添加元素
func (list *DoubleList) Push(value interface{}) bool {
	if value == nil {
		return false
	}
	node := &DoubleNode{
		Data: value,
	}
	list.mu.Lock()
	defer list.mu.Unlock()

	if list.Size == 0 {
		list.Head = node
		list.Tail = node
		node.Next = nil
		node.Prev = nil
	} else {
		node.Prev = list.Tail
		node.Next = nil
		list.Tail.Next = node
		list.Tail = node
	}
	list.Size++
	return true
}

// 尾部弹出元素
func (list *DoubleList) Pop() (value interface{}) {
	if list.Size == 0 {
		return nil
	}
	list.mu.Lock()
	defer list.mu.Unlock()

	node := list.Tail
	if list.Size == 1 {
		list.Head = nil
		list.Tail = nil
	} else {
		prevNode := node.Prev
		prevNode.Next = nil
		list.Tail = prevNode
	}
	list.Size--
	return node.Data
}

// 长度
func (list *DoubleList) Length() (len uint64) {
	return list.Size
}

// 头部插入节点
func (list *DoubleList) Unshift(value interface{}) bool {
	node := &DoubleNode{
		Data: value,
	}
	list.mu.Lock()
	defer list.mu.Unlock()

	if list.Size == 0 {
		list.Head = node
		list.Tail = node
	} else {
		node.Next = list.Head
		list.Head.Prev = node
		list.Head = node
	}
	list.Size++

	return true
}

// 头部弹出元素
func (list *DoubleList) Shift() (value interface{}) {
	if list.Size == 0 {
		return nil
	}

	list.mu.Lock()
	defer list.mu.Unlock()

	node := list.Head
	node.Next.Prev = nil
	list.Head = node.Next
	list.Size--

	return node.Data
}

// 在某个位置插入元素
func (list *DoubleList) Insert(index uint64, value interface{}) bool {
	if value == nil {
		return false
	}
	// 在尾部插入
	if index >= list.Size+1 {
		return list.Push(value)
	}
	// 在头部插入
	if index == 1 {
		return list.Unshift(value)
	}

	list.mu.Lock()
	defer list.mu.Unlock()

	node := &DoubleNode{
		Data: value,
	}
	var i uint64
	cur := list.Head
	for i = 1; i < index; i++ {
		cur = cur.Next

	}
	cur.Prev.Next = node
	node.Prev = cur.Prev
	cur.Prev = node
	node.Next = cur

	list.Size++

	return true
}

// 遍历元素
func (list *DoubleList) Travel() (res []interface{}) {
	if list.Size == 0 {
		return
	}

	node := list.Head
	res = append(res, node.Data)
	for node.Next != nil {
		node = node.Next
		res = append(res, node.Data)
	}

	return
}

// 入队列
func (list *DoubleList) Enqueue(value interface{}) bool {
	return list.Unshift(value)
}

// 出队列
func (list *DoubleList) Dequeue() (value interface{}) {
	return list.Pop()
}

func main() {
	queue := NewDoubleList()
	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	queue.Enqueue(4)

	queue.Insert(2, 8)
	list := queue.Travel()
	fmt.Println(list)

	a := queue.Dequeue()
	fmt.Println("a = ", a)
	queue.Dequeue()
	list = queue.Travel()
	fmt.Println(list)

	queue.Unshift(5)
	queue.Unshift(6)
	queue.Unshift(7)

	size := queue.Length()
	fmt.Println(size)

	list = queue.Travel()
	fmt.Println(list)

	value2 := queue.Shift()
	fmt.Println("value2 = ", value2)

	fmt.Println(queue.Travel())

	data := queue.Get(2)
	fmt.Println(data)

	value1 := queue.Pop()
	fmt.Println(value1)
}
